package com.clstu.hashtab;

import java.util.Scanner;

/**
 * 研究HashTab,哈希表(数组+链表的结构)的模拟和使用
 * 哈希表解决了链表的查询效率低的问题,也解决了数组的添加删除效率低的问题
 * 查询效率和添加删除效率都不错
 * HashTab 可以用来当作缓存使用,减少数据库的访问次数,
 */
public class HashTabDemo {
    public static void main(String[] args) {
        //测试
        //创建HashTab
        HashTab hashTab = new HashTab(8);
        //打印菜单法
        Scanner scanner = new Scanner(System.in);
        String key = "";//接受输入
        boolean loop = true;//控制循环
        int id = 0;//接受输入的id
        while (loop){
            //打印菜单
            System.out.println("========测试哈市表的使用======");
            System.out.println("    add: 添加数据");
            System.out.println("   list: 显示所有数据");
            System.out.println("   find: 查找数据");
            System.out.println(" delete: 删除数据");
            System.out.println("   exit: 退出系统");
            System.out.print("请输入:");
            key = scanner.next();
            switch (key){
                case "add"://添加
                    System.out.print("请输入id:");
                    id = scanner.nextInt();
                    System.out.print("请输入姓名:");
                    String name = scanner.next();
                    hashTab.add(new Emp(id,name));
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.print("请输入要查找的id:");
                    id = scanner.nextInt();
                    System.out.println(hashTab.findById(id));
                    break;
                case "delete":
                    System.out.print("请输入要删除的id:");
                    id = scanner.nextInt();
                    hashTab.deleteById(id);
                    break;
                case "exit":
                    loop = false;
                    break;
            }
        }
        System.out.println("退出程序!~~");
    }
}
/**
 * 员工节点类
 */
class Emp{
    private int id;//员工id
    private String name;//员工姓名
    private Emp next;//下一个节点
    //构造器
    public Emp(int id, String name){
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Emp getNext() {
        return next;
    }

    public void setNext(Emp next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

/**
 * 员工链表类(不带头节点的,即头节点也用于存放数据)
 */
class EmpLinkedList{
    private Emp head = null;//不带头节点版本,头节点也用于存放数据

    //编写方法添加数据,直接添加到尾部,不排序
    public void add(Emp emp){
        //先判断是否链表空
        if(head==null){
            head = emp;
            return;
        }
        //遍历到最后一个节点
        Emp curEmp = head;
        while (curEmp.getNext() != null){
            curEmp = curEmp.getNext();
        }
        //添加到尾部
        curEmp.setNext(emp);
    }

    //编写方法列出所有数据,返回所有数据组合成的字符串
    public String list(){
        //先判断是否链表空
        if(head == null) {
            return "链表空";
        }
        //遍历拼接字符串
        String resStr = "";
        Emp curEmp = head;
        while (curEmp != null){
            resStr = resStr+"==> id:"+curEmp.getId()+" name:"+curEmp.getName()+" ";
            //curEmp后移
            curEmp = curEmp.getNext();
        }
        return resStr;
    }

    //编写方法实现删除..(根据id
    public void deleteById(int id){
        //先判断链表是否空
        if (head == null){
            System.out.println("没有找到数据,失败");
            return;
        }
        //如果需要删除的是第一个数据
        if(head.getId() == id){
            //原先的head会因为不再被引用而被垃圾回收机制回收
            head = head.getNext();
            return;
        }
        //遍历找到删除节点的前一个,对其删除
        Emp curEmp = head;
        while (curEmp.getNext() != null){
            //如果找到
            if(curEmp.getNext().getId() == id){
                //curEmp.getNext()会因为再也没有变量引用它而被垃圾回收机制回收掉
                curEmp.setNext(curEmp.getNext().getNext());
                return;
            }
        }
        //如果没有找到
        System.out.println("没有找到数据,失败");
    }

    //编写方法实现查找,根据id.没有返回null
    public Emp findById(int id){
        //先判断是否链表空
        if(head==null){
            return null;
        }
        //遍历查找
        Emp curEmp = head;
        while (curEmp != null){
            //如果找到
            if(curEmp.getId() == id){
                return curEmp;
            }
            //后移
            curEmp = curEmp.getNext();
        }
        //没找到
        return null;
    }
}

/**
 * EmpHashTab类,存放的都是员工,是一个链表数组
 */
class HashTab{
    private EmpLinkedList[] empLinkedListArr= null;//链表数组
    private int size = 0 ;//链表数组的大小

    //构造器
    public HashTab(int size){
        this.size = size;
        empLinkedListArr = new EmpLinkedList[size];
        //注意,每一个链表也需要new 才能有空间,不然就是null
        for (int i = 0; i < size; i++) {
            empLinkedListArr[i] = new EmpLinkedList();
        }
    }

    //编写方法模拟简单的Hash函数,简单起见,根据id取模运算即可
    public int hashFuc(int id){
        return id % size;
    }

    //编写方法实现添加数据
    public void add(Emp emp){
        //根据hash值确定添加到哪一条链表
        int hs = hashFuc(emp.getId());
        empLinkedListArr[hs].add(emp);
    }

    //编写方法实现打印HashTab中的所有数据
    public void list(){
        for (int i = 0; i < size; i++) {
            System.out.println("第"+(i+1)+"条链表:"+empLinkedListArr[i].list());
        }
    }

    //编写方法实现查找某个数据,根据id,并显示一下再哪一条链表
    public Emp findById(int id ){
        //根据hash值确定去哪一条链表找
        int hash = hashFuc(id);
        System.out.println("在第"+(hash)+"条链表");
        return empLinkedListArr[hash].findById(id);
    }

    //编写方法删除数据
    public void deleteById(int id){
        //根据hash值判断到哪一条链表去删除
        int hash = hashFuc(id);
        empLinkedListArr[hash].deleteById(id);
    }
}